import java.util.*;

public class Text {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        //1. 单词计数
        for (String word: words) {
            if(hashMap.get(word) == null) {
                hashMap.put(word,1);
            }else {
                int val = hashMap.get(word);
                hashMap.put(word,val+1);
            }
        }
        // 将前K个出现次数高的单词放入小根堆中
        PriorityQueue<Map.Entry<String,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {
            if(heap.size() < k) {
                heap.add(entry);
            }else {
                // 判断大小 如果比堆顶元素大就往里放
                Map.Entry<String, Integer> top = heap.peek();
                if (entry.getValue().compareTo(top.getValue()) > 0) {
                    heap.poll();
                    heap.add(entry);
                }else {
                    if(entry.getValue().compareTo(top.getValue()) == 0) {
                        if(entry.getKey().compareTo(top.getKey()) < 0) {
                            heap.poll();
                            heap.add(entry);
                        }
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for(int i = 0; i < k;i++) {
            list.add(heap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {

    }
}
